package com.bm;

import com.future.util.TreeNode;

/**
 * Description: BM35 判断是不是完全二叉树
 *
 * @author weiruibai.vendor
 * Date: 2022/9/27 10:32
 */
public class BM35 {

    /**
     * {1,2,3,4,5,#,6}
     *
     * @param args
     */
    public static void main(String[] args) {
        BM35 bm35 = new BM35();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
        System.out.println(bm35.isCompleteTree(root));
    }

    /**
     * 完全二叉树的判断
     * <p>
     * 完全二叉树：设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边
     * （深度为k且有2^k-1个结点的二叉树称为满二叉树）
     * <p>
     * 假设头结点为x
     * 1、a的左树是满二叉树，右树是满二叉树，左高=右高
     * --------------a
     * ------------/  \
     * -----------b    c
     * ---------/  \  / \
     * -------d    e f   g
     * 2、a左完全二叉树，右满二叉树，左高=右高+1
     * -----------------a
     * --------------/   \
     * ------------b      c
     * ---------/  \    /  \
     * -------d    e   d'   e'
     * -----/\    /
     * ---f   g  h
     * 3、a左满，右满，左高=右高+1
     * -----------------a
     * --------------/   \
     * ------------b      c
     * ---------/  \    /  \
     * -------d    e   d'   e'
     * -----/\    / \
     * ---f   g  h   i
     * 4、a左满、右完全，左高=右高
     * -----------------a
     * --------------/    \
     * ------------b       c
     * ---------/  \     /  \
     * -------d    e    d'   e'
     * -----/\    / \  /\
     * ---f   g  h  i j  k
     */
    public boolean isCompleteTree(TreeNode root) {
        return process(root).isComplete;
    }

    private Info process(TreeNode root) {
        if (root == null) {
            return new Info(true, true, 0);
        }
        // 左边
        Info leftInfo = process(root.left);
        // 右边
        Info rightInfo = process(root.right);
        boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
        boolean isComplete = false;
        // 1、左、右边是满，且高度差<2 (注意，不能这样写left.height-right.height<2 因为这样不知道右边大还是左边大，现在是必须左边大于等于)
        if (leftInfo.isFull && rightInfo.isFull
                && (leftInfo.height == rightInfo.height || leftInfo.height == rightInfo.height + 1)) {
            isComplete = true;
        } else if (leftInfo.isComplete && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
            // 2、左完全，右边是满，左=右+1
            isComplete = true;
        } else if (leftInfo.isFull && rightInfo.isComplete && leftInfo.height == rightInfo.height) {
            // 3、左满，右完全，左=右
            isComplete = true;
        }
        return new Info(isFull, isComplete, Math.max(leftInfo.height, rightInfo.height) + 1);
    }


    class Info {
        public boolean isFull;

        public boolean isComplete;

        public Integer height;

        public Info(boolean isFull, boolean isComplete, Integer val) {
            this.isFull = isFull;
            this.isComplete = isComplete;
            this.height = val;
        }
    }
}
